package bTree.LeetCode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class 滑动窗口最大值 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int cnt=0;
        int maxCnt=nums.length-k;
        int []result=new int[maxCnt+1];
        Deque<Integer>deque=new LinkedList<>();
        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty()&&nums[deque.getLast()]<nums[i]){
                deque.removeLast();
            }
            deque.addLast(i);
        }
        result[cnt++]=nums[deque.getFirst()];
        for(int i=k;i<nums.length;i++){
            while (!deque.isEmpty()&&nums[deque.getLast()]<nums[i]){
                deque.removeLast();
            }
            if(!deque.isEmpty()&&i-deque.getFirst()>=k){
                deque.removeFirst();
            }
            deque.addLast(i);
            result[cnt++]=nums[deque.getFirst()];
        }
        return result;
    }
}